// 134.加油站
package Leetcode_Second_Brush;

public class Solution134 {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int length = gas.length;
        int[] remain = new int[length];

        for (int i = 0; i < length; i++) {
            remain[i] = gas[i] - cost[i];
        }

        int result = -1;
        for (int i = 0; i < length; i++) {
            int start = i;
            if (remain[start] < 0)
                continue;
            int sum = 0;
            int j = 0;
            for (j = 0; j < length; j++) {
                sum += remain[start];
                if (sum < 0)
                    break;
                start = (start + 1) % length;
            }

            if (j == length)
                result = start;
        }

        return result;
    }
}
